package algorithm.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 最大化利润
 *
 *
 * You are given an array prices where prices[i] is the price of a given stock on the ith day.
 *
 * You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
 *
 * Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
 *
 *
 *
 * Input: prices = [7,1,5,3,6,4]
 * Output: 5
 * Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
 * Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaxProfit {

    public static void main(String[] args) {
        int [] arr = {7,6,4,3,8};
        System.out.println(maxProfit(arr));
    }

    public static int maxProfit(int [] prices){
        Map<String, Integer> map = new HashMap<>();
        map.put("temporary", 0);

        if (prices.length == 1){
            return 0;
        }

        for (int i = 0; i < prices.length; i++) {
            for (int j = i+1; j < prices.length; j++) {
                if (Math.abs(prices[i] - prices[j]) < map.get("temporary")){
                    continue;
                }
                if (prices[i] - prices[j] >= 0){
                    //map.put("temporary", 0);

                    map.put("temporary", Math.max(0, map.get("temporary")));
                }else{
                    if (map.get("temporary") < Math.abs(prices[i] - prices[j]) ) {
                        map.put("temporary", Math.abs(prices[i] - prices[j]));
                    }
                }
            }
        }

        return map.get("temporary");
    }
}
